/*
 * @lc app=leetcode.cn id=310 lang=typescript
 *
 * [310] 最小高度树
 */

// @lc code=start
function findMinHeightTrees(n: number, edges: number[][]): number[] {
  const ans: number[] = [];
  // 只有一个节点
  if (n === 1) {
    ans.push(0);
    return ans;
  }
  // 初始化邻接表和节点出度
  const graph = new Array(n).fill(0).map(() => []);
  const outDegree = new Array(n).fill(0);
  for (const [u, v] of edges) {
    outDegree[u]++;
    outDegree[v]++;
    graph[u].push(v);
    graph[v].push(u);
  }
  // 广度优先搜索
  const queue: number[] = [];
  // 将出度为1的节点放入队列
  for (let i = 0; i < n; i++) {
    if (outDegree[i] === 1) queue.push(i);
  }
  // 最后一层节点是中间节点，也就是最小高度树的根节点
  while (queue.length) {
    const size = queue.length;
    ans.length = 0;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      ans.push(node);
      for (const neighbor of graph[node]) {
        outDegree[neighbor]--;
        if (outDegree[neighbor] === 1) queue.push(neighbor);
      }
    }
  }

  return ans;
}
// @lc code=end
